#include <stdio.h>
#include <stdlib.h>

#define InitSize 10     // 默认的最大长度
// 数据元素类型以整型为例，如果为结构体类型，则数据元素的比较不能直接使用`==``
typedef int ElemType_Tree;

// 定义顺序表
typedef struct {
    ElemType_Tree* data;     // 定义动态指针，指向第一个数据元素
    int maxSize;        // 当前顺序表的最大容量
    int length;         // 当前顺序表的长度
}SqList;



// 顺序表初始化
void InitSqList(SqList &L) {
    // 动态申请内存空间
    L.data = (ElemType_Tree*) malloc(sizeof (ElemType_Tree) * InitSize);
    L.maxSize = InitSize;
    L.length = 0;
}

// 顺序表动态拓展内存空间
void IncreaseSize(SqList &L, int addSize) {
    // 定义一个临时指针，存放数据
    ElemType_Tree *tmp = L.data;
    // 分配新的内存空间
    int NewMaxSize = L.maxSize + addSize;
    L.data = (ElemType_Tree*) malloc(sizeof (ElemType_Tree) * NewMaxSize);
    // 更新顺序表最大容量
    L.maxSize = NewMaxSize;
    // 将原内存空间中的数据元素放入新空间
    for (int i = 0; i < L.length; ++i) {
        L.data[i] = tmp[i];
    }
    // 释放原内存空间
    free(tmp);
}

// 顺序表的插入：在第pos个位置插入数据元素e
bool SqListInsertELem(SqList &L, int pos, ElemType_Tree e) {
    // 判断插入位置合法性
    if (pos < 1 || pos > L.length+1) {
        return false;
    }
    // 第pos个位置后面的数据元素全部后移一位
    for (int i = L.length; i >= pos; --i) {
        L.data[i] = L.data[i-1];
    }
    // 在第pos个位置插入数据元素e，顺序表长度+1
    L.data[pos-1] = e;
    L.length++;
    return true;
}

// 顺序表的删除：删除第pos个位置的数据元素，并通过指针e返回被删除的元素的值
bool SqListDeleteElem(SqList &L, int pos, ElemType_Tree &e) {
    // 判断插入位置合法性
    if (pos < 1 || pos > L.length) {
        return false;
    }
    // 获取到第pos个位置的元素
    e = L.data[pos-1];
    // 第pos个位置后面的数据元素全部前移一位
    for (int i = pos-1; i < L.length; ++i) {
        L.data[i] = L.data[i+1];
    }
    L.length--;
    return true;
}

// 顺序表的按位查找：返回指定位置的数据元素
ElemType_Tree SqListGetElemByPos(SqList &L, int pos) {
    // 判断插入位置合法性
    if (pos < 1 || pos > L.length) {
        return NULL;
    }
    // 返回第pos个位置的数据元素
    return L.data[pos-1];
}

// 顺序表的按值查找：返回指定值的数据元素的位置
// （此处以整型元素为例，复杂的数据元素不能直接用`==`判等）
int SqListGetElemByValue(SqList &L, ElemType_Tree e) {
    for (int i = 0; i < L.length; ++i) {
        if (e == L.data[i]) {
            return i+1;
        }
    }
    return NULL;
}


/**
 * 测试程序
 * @return
 */
int main() {
    printf("hello, SqList!\n");
    return 0;
}